ARC115 & CF709 题解

比赛

两场时间相同就并起来写了

还是 ARC 好啊

$ARC012$

$A$

显然 $(i, j)$ 不可能当且仅当 $bitcount(a_i \oplus a_j) = 2k (k \in Z)$，分讨一下发现后面这个满足当且仅当 $bitcount(a_i)$ 和 $bitcount(a_j)$ 的奇偶性相同。

$B$

无解随便判：令 $A_i = c_{i, 1} - a_1$, $B_j = c_{1, j} - b_1$, $a_i = a_1 + A_i$, $b_j = b_1 + B_j$，那么若 $c_{i, j} \neq c_{1, 1} + A_i + B_j$ 则无解。否则考虑 $a_1$ 和 $b_1$ 的取值，要保证所有 $a_i$ 和 $b_j$ 非负，$mna = \max(0, \max(-A_i))$, $mnb = \max(0, \max(-B_i))$，若 $mna + mnb > c_{1, 1}$ 则无解，否则取 $a_1 = mna$ 即可。

$C$

我是煞笔，直接写了个 $O(n \sqrt{n} + nlog^2n)$ 的二分 + 线段树，取 mex，好在 at 评测姬快如闪电。

正解有点小妙，将 $a_i$ 设为 $i$ 的质因数个数（重复算多个），这样一定满足 $a_{i 的因数} < a_i$。

$D$

首先如果是树的话，$k$ 为奇数无解，否则看作两两配对，答案就是 $\binom{n}{k}$；图呢答案就是 $2^{m - (n - 1)} \binom{n}{k}$。

因为选一条非树边，有几种情况：

  1. 如果连接两个黑点，这俩原先配对的就断了，变成他俩用这条非树边彼此配对
  2. 如果连接两个白点，可以先让这俩在树上路径上配对变黑，再用非树边让他俩变白
  3. 连接一黑一白，直接还是合法的

多个连通块，背包一下就好。

$E$

$dp_{i, j}$ 表示到第 $i$ 个，与其同色的有 $j$ 个。$dp_{nxt, j + nxt - i - 1} += dp_{i, j} * \min\limits_{k \in [i + 1, nxt]}( a_k )$

每个元素都有两种去处，一是归入已有块，二是自成一块。考虑单调栈维护已有块，越往前最小值一定是递减的，有元素进栈时就推平一块儿地顺便合并被推平块，成为新块，新块的值是推平块的值之和。

$F$

咕咕？

$CF709$

$A$

$\lceil \frac{m}{2} \rceil$ 意味着即使有不合法的小朋友也只有一个。于是先随便选，若不合法则在有选择余地的天里换人。

记录 xml 的手贱瞬间：换的是不合法小朋友被选中的那些天啊喂！

$B$

每次删除不会对其他位置造成影响。链表即可？不过我用的并查集。

$C$

用线段树——烦了！往前走，最小值递减，于是维护每个块的 $\max(dp_{i - 1})$。当前块有两种选择：

  1. 归入上一块，即 $dp_i = dp_{stk_{top - 1}}$
  2. 新成一块，即 $dp_i = Mx_{top} + b_i$

一个简单的单调栈就 AC 辣，是不是很奈思？

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 3e5 + 10;
ll n, h[N], b[N], dp[N], top, stk[N], Mx[N], f[N];

void cmax(ll &x, ll y) { x = max(x, y); }

int main() {
    cin >> n;
    rep(i, 1, n) scanf("%lld", &h[i]);
    rep(i, 1, n) scanf("%lld", &b[i]);
    dp[0] = -1e18;
    dp[1] = b[1];
    stk[top = 1] = 1;
    Mx[1] = 0;
    rep(i, 2, n) {
        ll mx = dp[i - 1];
        while (top && h[stk[top]] >= h[i]) {
            cmax(mx, Mx[top]);
            --top;
        }
        stk[++top] = i;
        Mx[top] = mx;
        dp[i] = max(dp[stk[top - 1]], mx + b[i]);
    }
    printf("%lld\n", dp[n]);
    return 0;
}

$D$

对于某对 $(u, v, l)$，$(x, y)$ 合法当且仅当 $dis_{u, x} + v_{x, y} + v_{y, v} \leq l$

枚举 $u$, $x$, $y$，$(x, y)$ 合法当且仅当 $dis_{u, x} + v_{x, y} \leq \max(l - v_{y, v})$

就做完了？大水题，真的是 div1 的 $D$ 嘛。。

$E$

咕咕

$F$

ACAM。广义 SAM 怎么做啊？

$s_j$ 在 $s_i$ 中出现，一定 $|s_j| \leq |s_i|$。我们枚举 $i$ 和 $i$ 中 $j$ 出现位置的右端点 $k$，
$s_j$ 一定是右端点为 $k$ 的左端点最小的串。$j$ 是好确定的——就是在 ACAM 上跑 $s_i$ 的时候，距离 $k$ 最近的整串位置。然后右端点在 $[k + 1, |s_i|]$ 的串的最小左端点还要大于 $k - |s_j| + 1$。

$s_j$ 对 $s_i$ 有贡献，当且仅当其在 $s_i$ 中出现的次数 $=$ 不被其他 $s_i$ 中出现串包含的出现次数（有点绕），左边这个用 BIT 维护 dfs 序，右边那个直接做就好啦。

$O((\sum |s_i|) log (\sum |s_i|))$

$Code$

ACAM 虽然没有 SAM 功能多，但处理模式匹配、部分子串问题就简洁许多。